package com.leetcode.binarytree;


import com.leetcode.datastructure.TreeNode;

/**
 * @author: ZhouBert
 * @date: 2019/10/12
 * @description:	687. 最长同值路径
 * A
 *
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:
输入:
5
/ \
4   5
/ \   \
1   1   5
输出:
2

示例 2:
输入:
1
/ \
4   5
/ \   \
4   4   5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
 */
public class LongestUnivaluePath687 {

	/**
	 * 由于求边，两个节点确定一条边。所以先用递归求出最长节点，再减去1
	 * --理解错了，以为是求长度。。。
	 * @param root
	 * @return
	 */
	public int longestUnivaluePath(TreeNode root) {
		if (root==null){
			return 0;
		}
		return longestUnivalueNode(root)-1;

	}

	/**
	 * 求最长节点
	 * @param root
	 * @return
	 */
	public int longestUnivalueNode(TreeNode root){
		if (root==null){
			return 0;
		}
		if (root.left==null&&root.right==null){
			return 1;
		}
		int leftLen = longestUnivalueNode(root.left);
		int rightLen = longestUnivalueNode(root.right);
		return Math.max(leftLen,rightLen)+1;
	}
}
